package com.yvon.service.demo.algorithm.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * 礼物的最大价值
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 */
public class P48 {

    public static void main(String[] args) {
        Solution solution = new P48().new Solution();
        int addfdvfgddassseeeeeeeee = solution.lengthOfLongestSubstring("addfdvfgddassseeeeeeeee");
        System.out.printf(addfdvfgddassseeeeeeeee + " ");
    }

    class Solution {
        /**
         * “滑动窗口 + 哈希表”。
         * 定义一个哈希表记录当前窗口内出现的字符，i、j 分别表示不重复子串的结束位置和开始位置，res 表示无重复字符子串的最大长度。
         * 遍历 i，若 [j, i - 1] 窗口内存在 s[i]，则 j 循环向右移动，更新哈希表，直至 [j, i - 1] 窗口不存在 s[i]，循环结束。将 s[i] 加入哈希表中，此时 [j, i] 窗口内不含重复元素，更新 res 的最大值：res = max(res, i - j + 1)。
         * 最后返回 res 即可。
         */
        public int lengthOfLongestSubstring(String s) {
            int res = 0;
            Set<Character> set = new HashSet<>();
            for (int i = 0, j = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                while (set.contains(c)) {
                    set.remove(s.charAt(j++));
                }
                set.add(c);
                res = Math.max(res, i - j +1);
            }
            return res;
        }
    }
}
